class Solution {
    // // 错误解法：暴力枚举
    // public int[] twoSum(int[] price, int target) {
    //     int[] ret = new int[2];
    //     for (int i = 0; i < price.length; i++) {
    //         for (int j = i+1; j < price.length; j++) {
    //             if (price[i]+price[j] == target) {
    //                 ret[0] = price[i];
    //                 ret[1] = price[j];
    //                 return ret;
    //             }
    //         }
    //     }
    //     return ret;
    // }

    public int[] twoSum(int[] price, int target) {
        int[] ret = new int[2];
        // 通过target的值来缩小范围遍历
        int left = 0;
        int right = price.length-1;
        while (left < right) {
            if (price[left]+price[right] > target) {
                // 大于目标值，得减小
                right--;
            } else if (price[left]+price[right] < target) {
                // 小于目标值。得增大
                left++;
            } else {
                ret[0] = price[left];
                ret[1] = price[right];
                break;
            }
        }
        return ret;
    }
}